package com.csdemos.algs.graphs;

import java.util.ArrayList;
import java.util.LinkedList;

public class AdjacencyListGraph implements Graph {
	
	class Edge {
		int v2;
		int weight;
		
		public Edge(int v) {
			v2 = v;
		}
		
		public Edge(int v, int w) {
			v2 = v;
			weight = w;
		}
		
		@Override
		public boolean equals(Object obj) {
			return ((Edge)obj).v2 == v2;
		}
	}
	
	private ArrayList<LinkedList<Edge>> vertexs;
	private int[] V;
	private boolean oriented;
	
	public AdjacencyListGraph(int n, boolean oriented) {
		vertexs = new ArrayList<LinkedList<Edge>>(n);
		this.oriented = oriented;
		V = new int[n];
		for (int i = 0; i < n; i++) {
			vertexs.add(new LinkedList<Edge>());
			V[i] = i;
		}
	}
	
	@Override
	public void addEdge(int v1, int v2) {
		addEdge(v1, v2, 0);
	}
	
	private void addEdgeOriented(int v1, int v2, int weight) {
		Edge e = new Edge(v2, weight);
		if (!vertexs.get(v1).contains(e)) {
			vertexs.get(v1).addFirst(e);
		}
	}
	
	@Override
	public void addEdge(int v1, int v2, int weight) {
		if (oriented) {
			addEdgeOriented(v1, v2, weight);
		} else {
			addEdgeOriented(v1, v2, weight);
			addEdgeOriented(v2, v1, weight);
		}
	}
	
	@Override
	public LinkedList<Integer> getAdjecents(Integer vertex) {
		LinkedList<Integer> result = new LinkedList<Integer>();
		for (Edge e : vertexs.get(vertex)) {
			result.add(e.v2);
		}
		return result;
	}
	
	@Override
	public int[] getVertexs() {
		return V;
	}
	
	@Override
	public Graph transpose() {
		AdjacencyListGraph graph = new AdjacencyListGraph(V.length, oriented);
		for (int i = 0; i < V.length; i++) {
			for (Edge e : vertexs.get(i)) {
				graph.addEdge(e.v2, i, e.weight);
			}
		}
		return graph;
	}
	
	@Override
	public int getWeight(int v1, int v2) {
		for (Edge e : vertexs.get(v1)) {
			if (e.v2 == v2) {
				return e.weight;
			}
		}
		if (!oriented) {
			for (Edge e : vertexs.get(v2)) {
				if (e.v2 == v1) {
					return e.weight;
				}
			}
		}
		return -1;
	}

}
